package com.ywk.base.dataStructure.binarytree;

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Queue;

//平衡二叉树：在二叉搜索树的基础上平衡根结点左右子树高度的算法
public class AVLTreeDemo {

	public static void main(String[] args) {
//		int[] arr= {4,3,6,5,7,8};//需要左旋转的数组
//		int[] arr= {10,12,8,9,7,6};//需要右旋转的数组
		int[] arr= {10,11,7,6,8,9};//需要双旋转的数组
		AVLTree at=new AVLTree();
		for(int i=0;i<arr.length;i++) {
			at.addNode(new AVLNode(arr[i]));
		}
		System.out.print("中序遍历：");
		at.infixOrder();
//		System.out.println("要寻找的目标节点："+at.search(5));
//		System.out.println("要寻找的目标节点的父节点："+at.searchPraentNode(at.search(5)));
//		at.deleteNode(5);
//		at.infixOrder();
		System.out.println();
		System.out.println("根结点："+at.getRoot());
		System.out.println("根结点高度："+at.height(at.getRoot()));
		System.out.println("根结点左子结点高度："+at.height(at.getRoot().left));
		System.out.println("根结点右子结点高度："+at.height(at.getRoot().right));
		
		List<List<Integer>> res=new LinkedList<List<Integer>>();
		res=at.levelOrder(at.getRoot());
		ListIterator<List<Integer>> it=res.listIterator();
		System.out.print("层次遍历：");
		while(it.hasNext()) {
			System.out.print(it.next());
		}
	}
}

class AVLTree{
	public AVLNode root;
	
	public AVLTree() {
		super();
	}
	
	public AVLTree(AVLNode root) {
		this.root=root;
	}
	
	public void addNode (AVLNode n) {
		if(root==null) {
			root=n;
		}else {
			root.addNode(n);
		}
	}
	
	public void deleteNode(int value) {
		AVLNode flag=search(value);
		if(flag==null) {
			return;
		}
		if(root.left==null&&root.right==null) {
			root=null;
			return;
		}
		AVLNode pre=searchPraentNode(flag);
		//删除的是叶子结点
		if(flag.left==null&&flag.right==null) {
			if(pre.left!=null&&pre.left.value==value) {
				pre.left=null;
			}else if(pre.right==flag) {
				pre.right=null;
			}
		//删除的结点只有一颗子树	
		}else if(flag.left==null&&pre.right==flag) {
			pre.right=flag.right;
		}else if(flag.right==null&&pre.right==flag) {
			pre.right=flag.left;
		}else if(flag.left==null&&pre.left==flag) {
			pre.left=flag.right;
		}else if(flag.right==null&&pre.left==flag) {
			pre.left=flag.left;
		}else {//删除的结点有两颗子树
			AVLNode minNode=flag.left;//在删除节点的左子树中找最大的数或在右子树中找最小值
			while(true) {
				if(minNode.right==null) {
					break;
				}
				minNode=minNode.right;
			}
			flag.value=minNode.value;
			if(minNode.left!=null) {
				searchPraentNode(minNode).right=minNode.left;
			}else {
				searchPraentNode(minNode).left=null;
			}
			
		}
	}
	
	//寻找目标结点
	public AVLNode search(int value) {
		if(root==null) {
			return null;
		}else {
			return root.search(value);
		}
	}
	
	//寻找目标结点的父节点
	public AVLNode searchPraentNode(AVLNode n) {
		if(root==null) {
			return null;
		}
		return root.searchParentNode(n);
	}
	
	public AVLNode getRoot() {
		return root;
	}
	
	//中序遍历
	public void infixOrder() {
		if(root==null) {
			return;
		}else {
			root.infixOrder();
		}
	}
	
	//层次遍历
	public List<List<Integer>> levelOrder(AVLNode root) {
        List<List<Integer>> res=new LinkedList<List<Integer>>();
        if(root==null){
            return res;
        }
        Queue<AVLNode> q=new LinkedList<>();
        int index=0;
        q.offer(root);
        while(q.size()>0){
            List<Integer> temp=new LinkedList<>();
            int len=q.size();
            for(int i=0;i<len;i++){
            	AVLNode cur=q.poll();
                temp.add(cur.value);
                if(cur.left!=null){
                    q.offer(cur.left);
                }
                if(cur.right!=null){
                    q.offer(cur.right);
                }
            }
            res.add(index,temp);
            index++;
        }
        return res;
    }
	
	//获得以该节点为根结点的树的高度
	public int height(AVLNode n) {
		if(n==null) {
			return 0;
		}
		return n.height();
	}
	
	//将二叉搜索树左旋转成平衡二叉树
	public void leftRotate() {
		if(root==null) {
			return;
		}
		AVLNode n=new AVLNode(root.value);
		n.left=root.left;
		n.right=root.right.left;
		root.value=root.right.value;
		root.right=root.right.right;
		root.left=n;
	}
	
}

class AVLNode{
	public int value;
	public AVLNode left;
	public AVLNode right;
	
	private int leftType;
	private int rightType;
	
	public AVLNode(int value) {
		super();
		this.value = value;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public AVLNode getLeft() {
		return left;
	}

	public void setLeft(AVLNode left) {
		this.left = left;
	}

	public AVLNode getRight() {
		return right;
	}

	public void setRight(AVLNode right) {
		this.right = right;
	}

	public int getLeftType() {
		return leftType;
	}

	public void setLeftType(int leftType) {
		this.leftType = leftType;
	}

	public int getRightType() {
		return rightType;
	}

	public void setRightType(int rightType) {
		this.rightType = rightType;
	}
	
	public void addNode(AVLNode n) {
		if(n==null) {
			return;
		}else {
			if(n.value<this.value) {
				if(this.left==null) {
					this.left=n;	
				}else {
					this.left.addNode(n);
				}
			}else {
				if(this.right==null) {
					this.right=n;
				}else {
					this.right.addNode(n);
				}
			}
		}
		//当根结点的左右子树高度的差值大于1时，需要调整成平衡二叉树
		if(this.left!=null&&this.right!=null) {
			//右旋转
			if(this.left.height()-this.right.height()>1) {
				//当需要处理双旋转的情况
				if(this.left.left.height()<this.left.right.height()) {
					this.left.leftRotate();
				}
				this.rightRotate();
			}
			//左旋转
			if(this.right.height()-this.left.height()>1) {
				//当需要处理双旋转的情况
				if(this.right.right.height()<this.right.left.height()) {
					this.right.rightRotate();
				}
				this.leftRotate();
			}
		}
	}
	
	public AVLNode search(int v) {
		AVLNode flagNode=null;
		if(v<this.value) {
			if(this.left!=null) {
				return this.left.search(v);//此处return不能略写（重点）
			}else {
				return null;
			}
		}else if(this.value==v){
			flagNode=this;
		}else {
			if(this.right!=null) {
				return this.right.search(v);
			}else {
				return null;
			}
		}
		return flagNode;
	}
	
	public AVLNode searchParentNode(AVLNode n) {
		AVLNode praent=null;
		if((this.left!=null&&n.value==this.left.value)||(this.right!=null&&n.value==this.right.value)) {
			praent=this;
		}else {
			if(n.value<this.value&&this.left!=null) {
				return this.left.searchParentNode(n);
			}else if(n.value>=this.value&&this.right!=null) {
				return this.right.searchParentNode(n);
			}else {
				return null;
			}
		}
		return praent;
	} 
	
	//中序遍历
	public void infixOrder() {
		if(this.left!=null) {
			this.left.infixOrder();
		}
		System.out.print(this);
		if(this.right!=null) {
			this.right.infixOrder();
		}
	}
	
	//将二叉搜索树左旋转成平衡二叉树
	public int height() {
		/*理解递归中的返回值：下一层的结果值返回给上一层调用它的地方。例：根节点为4，
		该节点的左结点为3,3没有子节点；从4开始递归，即此时this就是4,当第一次递归时，
		4的左结点不为空，从this.left.height()递归到下一级结点3，此时3的左右节点为空，
		return Math.max(0,0)+1，即将结果值1返回给调用它的地方，即上一级结点4的地方，此
		时结点4的 Math.max(1,)+1括号里面左边的值为1，然后进行右子树递归，同理右子树递
		归回到最开始的地方（即this为结点4处）得到 Math.max(1,3)+1，最后返回3+1=4*/
		return Math.max(this.left==null?0:this.left.height(), this.right==null?0:this.right.height())+1;
	}
	
	//将二叉搜索树左旋转成平衡二叉树
	public void leftRotate() {
		AVLNode n=new AVLNode(this.value);
		n.left=this.left;
		n.right=this.right.left;
		this.value=this.right.value;
		this.right=this.right.right;
		this.left=n;
	}
	
	//将二叉搜索树右旋转成平衡二叉树
	public void rightRotate() {
		AVLNode n=new AVLNode(this.value);
		n.right=this.right;
		n.left=this.left.right;
		this.value=this.left.value;
		this.left=this.left.left;
		this.right=n;
	}

	@Override
	public String toString() {
		return "[value=" + value + "] ";
	}
}